package pdd;

/**
 * Created by lingfengsan on 2018/9/17.
 *
 * @author lingfengsan
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Main main=new Main();
        ListNode node1=main.int2Node(new int[]{1,2,3});
        ListNode node2=main.int2Node(new int[]{1,2,3});
        ListNode node3=main.int2Node(new int[]{1,2,3});
        ListNode node=main.Merge(new ListNode[]{node1,node2,node3});
        while (node!=null){
            System.out.print(node.val+",");
            node=node.next;
        }
    }
    public ListNode int2Node(int[] nums){
        ListNode head=new ListNode(-1);
        ListNode temp=head;
        for (int num : nums) {
            temp.next=new ListNode(num);
            temp=temp.next;
        }
        return head.next;

    }
    public ListNode Merge(ListNode[] nodes) {
        ListNode res = nodes[0];
        for (int i = 1; i < nodes.length; i++) {
            res = Merge(res, nodes[i]);
        }
        return res;
    }
//递归
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) return list2; //判断到某个链表为空就返回另一个链表。如果两个链表都为空呢？没关系，这时候随便返回哪个链表，不也是空的吗?
        if (list2 == null) return list1;
        ListNode list0 = null;//定义一个链表作为返回值
        if (list1.val < list2.val) {//判断此时的值，如果list1比较小，就先把list1赋值给list0，反之亦然
            list0 = list1;
            list0.next = Merge(list1.next, list2);//做递归，求链表的下一跳的值
        } else {
            list0 = list2;
            list0.next = Merge(list1, list2.next);
        }
        return list0;
    }
//非递归
    public ListNode Merge1(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        ListNode tmp1 = list1;
        ListNode tmp2 = list2;
        ListNode head = new ListNode(0);//这里不能把返回链表赋值为null，因为下一行马上就要把它赋值给另一链表，得让它在内存里有位置才行
        ListNode headptr = head;
        while (tmp1 != null && tmp2 != null) {

            if (tmp1.val <= tmp2.val) {
                head.next = tmp1;
                head = head.next;
                tmp1 = tmp1.next;
            } else {
                head.next = tmp2;
                head = head.next;
                tmp2 = tmp2.next;
            }

        }
        //其中一个链表已经跑到头之后，继续单链表的合并
        while (tmp1 != null) {
            head.next = tmp1;
            head = head.next;
            tmp1 = tmp1.next;
        }
        while (tmp2 != null) {
            head.next = tmp2;
            head = head.next;
            tmp2 = tmp2.next;
        }
        head = headptr.next;
        return head;


    }


}
